Networks are moving away from services as long-term static end-to-end connections to on-demand services with dynamic end-to-end connections (“connections”). On-demand connections may be requested with fixed bandwidth requirements or with elastic bandwidth requirements, and they may have the requirement of starting immediately or delayed in time. Efficient build-up of on-demand networks considers the fact that not all traffic is on the network at the same time. In other words, the network design takes into consideration the statistical multiplexing of end-to-end connections on a link and network level and allocates less capacity than is required to run all traffic at its peak bandwidth. Naturally, there may be times of congestion when many of the traffic flows do come into the network and cause a temporary overload.
With this type of network in mind, it is clear that static path computation or path computation which does not consider the network status may cause problems in the times of congestion. Consider shortest-path path computation in a network that has a bottleneck link for many paths, during the times of congestion, this link will become overloaded, causing blocking. If there are many bottleneck links in the network, fixed path computation may cause loss of throughput. This may happen if some connections are put on their shortest path, when in fact they should have been routed alternatively to keep the shortest path clear for other connections. One example where this may happen is if short-term connections are allocated bandwidth on bottleneck links and are blocking long-term connections from entering the network. This type of resource allocation may cause lower throughput and revenue over the long run, if once the short-term connections leave the network the long-term connections have moved on to another service provider.
To prevent throughput loss, path computation for on-demand connections should at least observe the current network status when finding paths for new connections to avoid full utilization of bottle-neck links. A typical path computation approach with network status information is an adaptive path computation, which adds a penalty on the links with high utilization so that shortest-path algorithms avoid the link in the times of congestion. This solves the previous problem of blocking shortest paths too soon into congestion. The adaptive path computation approach routes a connection to avoid blocking bottleneck links, leaving some free bandwidth on these links, if the congestion increases further. However, in the times of overload, this approach may cause “throughput collapse” in the network. Throughput collapse happens if too many connections are routed on long paths. This causes a congestion positive feedback loop, where links which would normally not be congested due to traffic patterns (the overload traffic patterns) now become congested due to congestion avoidance of the adaptive path computation, causing links throughout the network to block. In the case of overload, the path computation should perform some actions to prevent network-wide link blocking.
The aforementioned path computation problems related to when the connections require instantaneous bandwidth. However, these problems also exist when the connections will require bandwidth in the future. Indeed, any type of path computation for on-demand networks should use the knowledge of the future network status and future forecast network status, when scheduling connections in the future to prevent future link blocking. It may also need to perform actions to prevent future throughput collapse. However, conventional approaches in adaptive routing and path computation do not consider future knowledge of the network status, which is necessary to prevent congestion from future traffic as well as connection rejection mechanisms which prevent throughput collapse.